/*
 * 0221. 链表求和 II
 * 假定用一个链表表示两个数，其中每个节点仅包含一个数字。假设这两个数的数字顺序排列，请设计一种方法将两个数相加，并将其结果表现为链表的形式。
 * https://www.lintcode.com/problem/add-two-numbers-ii/description
 * 
 * 样例
 * 给出 6->1->7 + 2->9->5。即，617 + 295。
 * 返回 9->1->2。即，912 。
 * 
 * 2018.06.25 @jeyming
 */
package wo_numbers_ii_0221;

//Definition for ListNode
class ListNode {
	int val;
	ListNode next;
	ListNode(int x) {
		val = x;
		next = null;
	}
}

public class Wo_numbers_ii_0221 {
	/**
	 * @param l1: The first list.
	 * @param l2: The second list.
	 * @return: the sum list of l1 and l2.
	 */
	public ListNode addLists2(ListNode l1, ListNode l2) {
		// write your code here
		String a = "";
		String b = "";
		ListNode p = l1;
		ListNode q = l2;
		while((p != null) || (q != null)) {
			if(p != null) {
				a += (p.val);
				p = p.next;
			}
			if(q != null) {
				b += (q.val);
				q = q.next;
			}
		}
		String res = "";
		int tmp = 0;
		int i = a.length() - 1;
		int j = b.length() - 1;
		while((i >= 0) || (j >= 0) || (tmp > 0)) {
			if((i < 0) && (j >= 0)) {
				tmp += b.charAt(j--) - '0';
			} else if((j < 0) && (i >= 0)) {
				tmp += a.charAt(i--) - '0';
			} else if((i >= 0) && (j >= 0)) {
				tmp += a.charAt(i--) + b.charAt(j--) - '0' - '0';
			}
			res += (tmp % 10);
			tmp /= 10;
		}
		ListNode resNode = new ListNode(res.charAt(res.length() - 1) - '0');
		p = resNode;
		for(int x = res.length() - 2; x >= 0; --x) {
			ListNode node = new ListNode(res.charAt(x) - '0');
			p.next = node;
			p = p.next;
		}
		return resNode;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
